package 代码记录.指定公司代码练习记录.华为_2024.分值100.第36start;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author zx
 * @create 2024-02-16 13:17
 * 看懂人家的代码了，但是这道题的题意看起来有的迷；代码还行，能看懂
 */
public class 生成哈夫曼树_65 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Node> nodes = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            nodes.add(new Node(sc.nextInt()));
        }
        Node root = buildHuffmanTree(nodes);
        List<Integer> res = new ArrayList<>();
        inOrder(root, res);
        //人家这个输出方式值得学习
        System.out.println(String.join(" ", res.stream().map(String::valueOf).toArray(String[]::new)));
    }

    //构建哈夫曼树并返回根节点
    //此方法通过对节点列表进行排序(按节点值升序),不断取两个最小的节点合并成新节点,直到只剩下一棵树,即哈夫曼树的根节点
    private static Node buildHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            nodes.sort(Node::compareTo);
            Node newNode = new Node(nodes.get(0).val + nodes.get(1).val);
            newNode.left = nodes.remove(0);
            newNode.right = nodes.remove(0);
            nodes.add(newNode);
        }
        return nodes.get(0);
    }

    //中序遍历并将结果存储到res中
    private static void inOrder(Node root, List<Integer> list) {
        if(root == null){
            return;
        }
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }

    static class Node implements Comparable<Node> {
        int val;
        Node left;
        Node right;

        public Node(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        //重写compareTo方法，既可以通过节点值进行排序
        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.val, other.val);
        }
    }
}
